package easy;

import java.util.HashSet;
import java.util.Set;

public class L136_只出现一次的数字 {

    /**
     * 异或运算. 任何数^0=数本身，数字a^数字a=0，且满足交换律和结合律.
     *
     * 执行用时：1 ms, 击败了100.00%的用户
     * 内存消耗：38.4 MB, 击败了79.53%的用户
     */
    public int singleNumber(int[] nums) {
        int res = 0;

        for (int num:nums){
            res ^= num;
        }

        return res;
    }

    /**
     * 使用set.
     *
     * 执行用时：11 ms, 击败了14.69%的用户
     * 内存消耗：38.6 MB, 击败了46.40%的用户
     */
    public int singleNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int num : nums){
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }

        for (int s: set) {
            return s;
        }
        return 0;
    }
}
